package LeetCode.leetcode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * 设计一个 在屏幕尺寸 =宽度 x 高度 的设备上玩 的贪吃蛇游戏。  如果您不熟悉游戏，请在线玩游戏。
 *
 * 蛇最初位于左上角 (0,0)，长度 = 1 个单位。
 *
 * 您将获得按行列顺序排列的食物位置列表。当一条蛇吃掉食物时，它的长度和游戏的分数都增加了 1。
 *
 * 每种食物一一出现在屏幕上。例如，直到第一个食物被蛇吃掉后，第二个食物才会出现。
 *
 * 当食物确实出现在屏幕上时，保证它不会出现在被蛇占据的方块上。
 * ————————————————
 * 版权声明：本文为CSDN博主「jmspan」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/jmspan/article/details/51688859
 *
 * 给定宽度 = 3，高度 = 2，食物 = [[1,2],[0,1]]。
 *
 * Snake 蛇 = new Snake(width, height, food);
 *
 * 最初，蛇出现在位置 (0,0)，食物出现在 (1,2)。
 *
 * |S| | |
 * | | |F|
 *
 * 蛇.move("R"); -> 返回 0
 *
 * | |S| |
 * | | |F|
 *
 * 蛇.move("D"); -> 返回 0
 *
 * | | | |
 * | |S|F|
 *
 * 蛇.move("R"); -> 返回 1（蛇吃第​​一个食物，然后，第二个食物出现在 (0,1) ）
 *
 * | |F| |
 * | |S|S|
 *
 * 蛇.move("U"); -> 返回 1
 *
 * | |F|S|
 * | | |S|
 *
 * 蛇.move("L"); -> 返回 2（蛇吃第二个食物）
 *
 * | |S|S|
 * | | |S|
 *
 * 蛇.move("U"); -> 返回 -1（游戏结束，因为蛇与边界碰撞）
 * ————————————————
 * 版权声明：本文为CSDN博主「jmspan」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/jmspan/article/details/51688859
 * @author leiwenkang <leiwenkang@kuaishou.com>
 * Created on 2022-08-01
 */
public class Test353贪吃蛇 {

    private Set<String> board = new HashSet<>();
    private int[][] food;
    private int eat = 0;
    private LinkedList<Position> snake = new LinkedList<>();
    private int width, height;

    private boolean eat(int y, int x) {
        if (eat >= food.length) {
            return false;
        }
        if (food[eat][0] < 0 || food[eat][0] >= height || food[eat][1] < 0 || food[eat][1] >= width) {
            return false;
        }
        if (y == food[eat][0] && x == food[eat][1]) {
            return true;
        }
        return false;
    }

    /**
     * Initialize your data structure here.
     *
     * @param width - screen width
     * @param height - screen height
     * @param food - A list of food positions
     * E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0].
     */
    public Test353贪吃蛇(int width, int height, int[][] food) {
        this.food = food;
        Position head = new Position(0, 0);
        this.snake.add(head);
        board.add(head.toString());
        this.height = height;
        this.width = width;
    }

    /**
     * Moves the snake.
     *
     * @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
     * @return The game's score after the move. Return -1 if game over.
     * Game over when snake crosses the screen boundary or bites its body.
     */
    public int move(String direction) {
        Position head = snake.getFirst();
        Position next = new Position(head.y, head.x);
        if ("U".equals(direction)) {
            next.y--;
        } else if ("D".equals(direction)) {
            next.y++;
        } else if ("L".equals(direction)) {
            next.x--;
        } else if ("R".equals(direction)) {
            next.x++;
        } else {
            return -1;
        }
        if (next.y < 0 || next.y >= height || next.x < 0 || next.x >= width) {
            return -1;
        }
        String ns = next.toString();
        if (eat(next.y, next.x)) {
            snake.addFirst(next);
            board.add(ns);
            return ++eat;
        }
        Position tail = snake.getLast();
        board.remove(tail.toString());
        snake.removeLast();
        if (board.contains(ns)) {
            return -1;
        }
        snake.addFirst(next);
        board.add(ns);
        return eat;
    }
}

class Position {
    int y, x;

    Position(int y, int x) {
        this.y = y;
        this.x = x;
    }

    public String toString() {
        return y + "," + x;
    }
}